/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-12-25
 * Time: 22:19
 *//*


//  7-12 数塔  (C++版本)


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

        vector<vector<int>> list;

        void func(vector<vector<int>>& arr) {
        int len = arr.size();

        for (int i = len - 1; i >= 0; --i) {
        vector<int> array;

        int ret = i + 1;

        for (int j = 0; j < ret; ++j) {
        if (i == len - 1) {
        array.push_back(arr[i][j]);
        } else {
        break;
        }
        }

        for (int j = 0; j < ret; ++j) {
        if (i != len - 1) {
        int a = arr[i][j] + list.back()[j];
        int b = arr[i][j] + list.back()[j + 1];

        int big = max(a, b);
        array.push_back(big);
        } else {
        break;
        }
        }

        list.push_back(array);
        }
        }

        int main() {
        int t;
        cin >> t;

        for (int m = 0; m < t; ++m) {
        int n;
        cin >> n;
        vector<vector<int>> arr(n, vector<int>(n));

        for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i + 1; ++j) {
        cin >> arr[i][j];
        }
        }

        func(arr);
        int p = list.back()[0];
        cout << p << endl;
        list.clear();
        }

        return 0;
        }

*/
